package com.ycl.javacore.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * User: OF1089 杨成龙
 * Date: 2019/7/30
 * Time: 10:12 PM
 * Desc: 类描述
 */
public class LRUCache02 {
    private class Node {
        private int key;
        private int value;
        private Node next;
        private Node prev;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private int size;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head;
    private Node tail;

    public LRUCache02(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    private int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node cur = map.get(key);
        remove(key);
        add2head(key, cur.value);
        return cur.value;
    }


    private void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(key);
            add2head(key, value);
        } else {
            add2head(key, value);
        }
    }

    private void remove(int key) {
        Node cur = map.get(key);
        Node next = cur.next;
        Node prev = cur.prev;
        next.prev = prev;
        prev.next = next;
        size--;
        map.remove(key);
    }

    private void add2head(int key, int value) {
        Node newNode = new Node(key, value);
        Node next = head.next;
        newNode.next = next;
        next.prev = newNode;
        head.next = newNode;
        newNode.prev = head;
        size++;
        map.put(key, newNode);
        if (size > capacity) {
            Node prevTail = tail.prev;
            remove(prevTail.key);
        }
    }
}
